package 面试;


import java.util.*;

/**
 * 变位词组
 *
 * 编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
 */

public class L1002_new {

    public static void main(String[] args) {
        List<List<String>> lists = new L1002_new().groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s + " ");
            }
            System.out.println();
        }
    }

    /**
     * 思路：先遍历数组，把拿到的字符串进行排序，把排序好的作为 key 存进map中，value 则作为和这个key相同的集合
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {

        List<List<String>> lists = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();

        if (strs.length == 0) return lists;

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String sort = String.valueOf(chars);
            if (map.containsKey(sort)) {
                List<String> strings = map.get(sort);
                strings.add(s);
            }else {
                List<String> list = new ArrayList<>();
                list.add(s);
                map.put(sort, list);
            }
        }

        Set<String> strings = map.keySet();
        for (String s : strings) {
            lists.add(map.get(s));
        }
        return lists;
    }
}
